import Heap from "./abstractHeap";
import { Compare } from "./abstractHeap";

/**
 * #### 最小堆
 * @author liXin
 * @since 2025-04-11 08:49
 * @description 最小堆的根节点是所有元素中最小的，且每个节点的值都小于或等于其子节点的值
 * @see https://gitee.com/Lidppp/java-script-data-structure-and-algorithm/blob/master/Heap/MinHeap.ts
 */
class MinHeap<T> extends Heap<T> {
  insert(value: T): boolean {
    if (!value) {
      this.heap.push(value);
      this.siftUp(this.heap.length - 1);
      return true;
    }
    return false;
  }

  extract() {
    if (this.isEmpty()) return void 0;
    if (this.heap.length === 1) return this.heap.shift();
    const remove = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.siftDown(0);
    return remove;
  }

  siftUp(index: number) {
    let el = index;
    let left = Heap.getLeftIndex(el);
    let right = Heap.getRightIndex(el);
    let size = this.size();
    if (
      left < size &&
      this.compareFun(this.heap[el], this.heap[left]) === Compare.BIGGER_THAN
    ) {
      el = left;
    }
    if (
      right < size &&
      this.compareFun(this.heap[el], this.heap[right]) === Compare.BIGGER_THAN
    ) {
      el = right;
    }
    if (el !== index) {
      Heap.swap(this.heap, index, el);
      this.siftUp(el);
    }
  }

  siftDown(index: number) {
    let parentIndex = Heap.getParentIndex(index);
    while (
      index > 0 &&
      parentIndex &&
      this.compareFun(this.heap[parentIndex], this.heap[index]) ===
        Compare.BIGGER_THAN
    ) {
      Heap.swap(this.heap, parentIndex, index);
      index = parentIndex;
      parentIndex = Heap.getParentIndex(index);
    }
  }
}

export default MinHeap;
